package com.lmf.Stack.InversePolishCalculator;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 模拟实现一个，逆波兰计算器：暂不支持小数
 */
public class InversePolishCalculator {

    public static void main(String[] args) {
        //1.先将一个中缀表达式（即，人类正常使用的数学表达式），手动转换为一个后缀表达式（即，逆波兰表达式）
        //例：（30-5）*2+20 --->  30 5 - 2 * 20 + //70
        //例：（3-5）*2+20 --->  3 5 - 2 * 20 + //16
        String expression = "3 5 - 2 * 20 +";

        //2.从左至右扫描，遇见数字，直接进入数栈，一旦中间遇见字符，就从数栈中取出两个数进行运算，然后再将计算结果存入数栈
        int res = calExpression(expression);
        System.out.println("逆波兰表达式计算结果："+res);
        System.out.println("----------------------");


        //4.实现中缀表达式转换为后缀表达式
        //创建计算表达式
//        String expression3 = "1+((2+3)*4)-5";//16
        String expression3 = "1+((2+3)*4*2)-5";//36
        //将计算表达式转换为中缀表达式：利用集合
        ArrayList<String> list = parseStringToList(expression3);
        System.out.println("中缀表达式集合："+list);
        System.out.println("----------------------");
        //将这个集合转换为逆波兰表达式：返回集合
        ArrayList<String> list1 = parseStringToPolishInfo(list);
        System.out.println("逆波兰表达式集合："+list1);
        System.out.println("----------------------");
        //将逆波兰表达式转换为，中间加上空格分隔符形式，放到String里面
        String s = parseListToString(list1);
        System.out.println("逆波兰表达式字符串："+s);
        System.out.println("---------------");
        //计算这个逆波兰表达式的结果
        int res2 = calExpression(s);
        System.out.println(res2);
    }

    //计算逆波兰表达式的结果
    public static int calExpression(String expression){
        //1.先将字符串转换为一个数组：利用分割符方法
        String[] split = expression.split(" ");
        //2.再将数组转换为一个list集合：利用增强for循环
        ArrayList<String> list = new ArrayList<>();
        for (String s : split) {
            list.add(s);
        }

        //3.再遍历list集合
        //从左至右扫描，遇见数字，直接进入数栈，一旦中间遇见字符，就从数栈中取出两个数进行运算，然后再将计算结果存入数栈
        //创建一个栈，用来存储数
        Stack<Integer> stack = new Stack<>();
        for (String s : list) {
            //利用正则表达式来判断是否为数字类型字符串（包括多位数）,若是数字，直接进栈
            if (s.matches("\\d+")) {
                //注意：要先将数字类型字符串，转换为int类型,再进栈
                stack.push(Integer.parseInt(s));
            }else {
                //其他不是数字类型的字符串，就从数栈中取出两个数进行运算，然后再将计算结果存入数栈
                int num2 = stack.pop();     //数栈弹出的第一个数
                int num1 = stack.pop();     //数栈弹出的第二个数
                int res = 0; //用于接收运算结果

                //根据判断是哪种类型字符串，然后分别进行运算
                if (s.equals("+")) {
                    res = num1+num2;       //注意num1 ，num2的前后顺序
                }else if (s.equals("-")){
                    res = num1-num2;
                }else if (s.equals("*")){
                    res = num1*num2;
                }else if (s.equals("/")){
                    res = num1/num2;
                }

                //运算完后，将结果存入数栈
                stack.push(res);
            }
        }
        //当for循环完之后，数栈里面就只剩一个数，那就是结果
        return stack.pop();
    }

    //将计算表达式，转换为一个字符集合(中缀表达式)，方便运用
    public static ArrayList<String> parseStringToList(String expression){
        //创建一个栈，一个集合
        ArrayList<String> list = new ArrayList<>();     //存放中间结果栈
        String ch = "";  //存放每次取出的字符
        int index = 0;
        //1.先将一个完整计算表达式转换一个list集合，方便运用
        //即，1+((2+3)*4)-5  =>  ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
        while (index < expression.length()){
            ch = expression.substring(index,index+1);
            list.add(ch);
            index++;
        }
        return list;
    }

    //将中缀表达式转换为后缀表达式:即，自动将计算表达式转换为逆波兰表达式
    public static ArrayList<String> parseStringToPolishInfo(ArrayList<String> list){
        //创建一个栈，一个集合
        Stack<String> stack = new Stack<>();    //符号栈：s1栈
        ArrayList<String> list2 = new ArrayList<>();     //存放中间结果栈：s2栈

        //遍历整合集合
        for (String item : list) {
            if (item.matches("\\d+")) {
                //判断如果是多位数(数字类型字符串)，直接进 s2栈
                list2.add(item);
            }else if (item.equals("(") || stack.size() == 0) {
                //如果字符是操作符，分情况讨论
                //1.如果stack1为空，或者栈顶为“（”，则直接进s1栈
                stack.push(item);
            }else if(item.equals(")")){
                //2.当遇见“)”时，依次弹出s1栈的运算符，并压入s2栈，直到遇到“（”为止，此时将这一括号丢弃
                while (!stack.peek().equals("(")){
                    list2.add(stack.pop());
                }
                stack.pop();
            }else {
                //3.若栈不为空，当该操作符的优先级，小于等于栈顶运算符优先级的时候，则弹出符号栈的栈顶字符，并将它添加到s2栈中，
                // 再将该操作符添加进符号栈
                //4.若优先级大于栈顶操作符优先级，则直接进s1栈
                while (stack.size() != 0 && priority(item) <= priority(stack.peek())){
                    list2.add(stack.pop());
                }
                stack.push(item);
            }
        }
        //当将计算表达式，分别全部装入两个栈的时候；再将是s1栈，依次添加进s2栈
        //s2栈的逆序就是逆波兰表达式，但是本人这里使用集合，所以就不用反转顺序了，若使用栈，就必须反转一下
        while (stack.size() > 0){
            list2.add(stack.pop());
        }

        //返回s2栈
        return list2;
    }

    //将后缀表达式转换为一个以空格间距的字符串
    public static String parseListToString(List<String> list){
        String str = "";
        for (String s : list) {
            str += " " + s;
        }
        //注意：必须去掉字符串前面的空字符串
        //substring():是左闭右开区间
        String substring = str.substring(1, str.length());
        return substring;
    }

    //判断运算符优先级方法,数字越大，优先级越大
    public static int priority(String num){
        int res = 0;
        if (num.equals("*") || num.equals("/")) {
            res = 2;
        }else if (num.equals("+") || num.equals("-")){
            res = 1;
        }
        return res;
    }
}
